package tree.tire;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname : PrefixAndSuffixSearch
 * @Description :
 * <a href="https://leetcode.cn/problems/prefix-and-suffix-search/">745. 前缀和后缀搜索</a>
 * @Author : chentianyu
 * @Date 2023/1/18 16:01
 */


public class WordFilter {
    private Trie trie;

    public WordFilter(String[] words) {
        trie = new Trie();
        for (int i = 0; i < words.length; i++) {
            // 每个单词都要从根节点开始初始化
            Trie cur = trie;
            // 获取当前单词及其长度
            String word = words[i];
            int len = word.length();
            // 对当前单词字典树初始化
            // 搜索时最复杂情况 前缀 和 后缀 至少有一个就是当前单词
            for (int j = 0; j < len; j++) {
                Trie tmp = cur;
                // 初始化搜索到当前节点时只剩下前缀还有字母的字典树
                for (int k = j; k < len; k++) {
                    String key = new StringBuilder().append(word.charAt(k)).append('#').toString();
                    // 维护子节点
                    tmp.children.put(key, tmp.children.getOrDefault(key, new Trie()));
                    // 移动到子节点
                    tmp = tmp.children.get(key);
                    // 记录当前节点所属单词的下标，后面单词可能会覆盖前面单词，不过题目要求返回“最大下标”的单词
                    tmp.index = i;
                }
                tmp = cur;
                // 初始化搜索到当前节点时只剩下后缀还有字母的字典树
                for (int k = j; k < len; k++) {
                    String key = new StringBuilder().append('#').append(word.charAt(len - 1 - k)).toString();
                    tmp.children.put(key, tmp.children.getOrDefault(key, new Trie()));
                    tmp = tmp.children.get(key);
                    tmp.index = i;
                }
                // 初始化搜索到当前节点时前后缀都有字母的字典树
                String key = new StringBuilder().append(word.charAt(j)).append(word.charAt(len - 1 - j)).toString();
                cur.children.put(key, cur.children.getOrDefault(key, new Trie()));
                cur = cur.children.get(key);
                cur.index = i;
            }
        }
    }

    public int f(String pref, String suff) {
        Trie cur = trie;
        // 取前后缀的最大长度，逐个字母进行搜索
        int len = Math.max(pref.length(), suff.length());
        for (int i = 0; i < len; i++) {
            char prefChar = i >= pref.length() ? '#' : pref.charAt(i);
            char suffChar = i >= suff.length() ? '#' : suff.charAt(suff.length() - 1 - i);  // 注意后缀获取字母的方式
            String key = new StringBuilder().append(prefChar).append(suffChar).toString();
            if (cur.children.get(key) == null) return -1;
            cur = cur.children.get(key);
        }
        return cur.index;
    }


    class Trie {
        // 孩子节点通过Map组织
        Map<String, Trie> children;
        // 记录当前节点所属的单词下标
        int index;

        Trie() {
            children = new HashMap<>();
            index = -1;
        }
    }
}
